/**
 * 给你两个字符串s1和s2 ，写一个函数来判断 s2 是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。
 *
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 *
 * 链接：https://leetcode.cn/problems/permutation-in-string
 */
class CheckInclusion {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int count = 0;
        int[] need = new int[256];
        int[] window = new int[256];
        
          for(int i = 0; i< s1.length(); i++){
            
            if(need[s1.charAt(i)] == 0){
                count++;
            }
            need[s1.charAt(i)] += 1;
            
        }
        
        int left = 0, right = 0;
        int vaild = 0;
        while(right < s2.length()){
            char c = s2.charAt(right);
            right++;
            if(need[c] > 0){
                window[c]++;
                if(window[c] == need[c]){
                    
                    vaild++;
                }
            }
            
            while(right - left == n){
                if(vaild == count){
                    return true;
                }
                char d = s2.charAt(left);
                left++;
                if(need[d] > 0){
                    if(window[d] == need[d] ){
                        vaild--;
                    }
                    window[d]--;
                }
            }
            
        }
        
        return false;
    }
}